/**
 * 144. 二叉树的前序遍历
 *
 * 【简单】
 *
 * 给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
 *
 * 示例 1：
 * 【https://assets.leetcode.com/uploads/2020/09/15/inorder_1.jpg】
 * 输入：root = [1,null,2,3]
 * 输出：[1,2,3]
 *
 * 示例 2：
 * 输入：root = []
 * 输出：[]
 *
 * 示例 3：
 * 输入：root = [1]
 * 输出：[1]
 *
 * 示例 4：
 * 【https://assets.leetcode.com/uploads/2020/09/15/inorder_5.jpg】
 * 输入：root = [1,2]
 * 输出：[1,2]
 *
 * 示例 5：
 * 【https://assets.leetcode.com/uploads/2020/09/15/inorder_4.jpg】
 * 输入：root = [1,null,2]
 * 输出：[1,2]
 */

import { TreeNode } from '../utils/tree'

// 递归
var preorderTraversal = function preorderTraversal(
	root: TreeNode | null
): number[] {
	if (root == null) {
		return []
	}
	const res: number[] = []
	const dfs = (root: TreeNode | null) => {
		if (root == null) {
			return
		}
		res.push(root.val)
		if (root.left) {
			dfs(root.left)
		}
		if (root.right) {
			dfs(root.right)
		}
	}
	dfs(root)
	return res
}

// 迭代
var preorderTraversal = function preorderTraversal(
	root: TreeNode | null
): number[] {
	if (root == null) {
		return []
	}
	const res: number[] = []
	const stack = [root]
	while (stack.length) {
		root = stack.pop()!
		res.push(root.val)
		if (root?.right) {
			stack.push(root?.right)
		}
		if (root?.left) {
			stack.push(root?.left)
		}
	}

	return res
}
